#合并num1,num2，递增顺序
from typing import List


#非递减有序数组
nums1 = [1,2,3,0,0,0]
nums2 = [2,5,6]
# nums3 = [4,5,6]

m = 3
n = 3
# j = 0
# def expend_list(lis):
#     return [x for x in lis if x!=0]
#
#
# result = expend_list(nums1)
# for i in range (n):
#     while j<=m and nums2[i] > nums1[j]:
#         j += 1
#     else:
#         result.insert(j+i,nums2[i])
#         i+=1
# nums1 = result
# print(nums1)

###上面这个是正确的，但是要求原地修改不需要新建result


#方法二：
# nums1 = [1,2,3,0,0,0]
# nums2 = [2,5,6]
#
#
# m = 3
# n = 3
# j = 0
# def expend_list(lst,target_length):
#     return lst + [0] * (target_length - len(lst))
#
# nums1=expend_list(nums1,n+m)
#
# #[1,2,3,0,0,0]
# #[2,5,6]
# for i in range (n):
#     while j<m and  nums2[i] > nums1[j]:
#         j += 1
#     else:
#         if j==m:
#             nums1[m+1:]=nums2[i:]
#             break
#         nums1.insert(j+i,nums2[i])
#         i+=1
#
# print(nums1)


# nums1=[4,0,0,0,0,0]
# m=1
# nums2=[1,2,3,5,6]
# n=5

j = 0

# 直接使用nums1的前m个元素，后n个位置用于合并
for i in range(n):
    # 找到nums2[i]应该插入的位置j
    while j < m + i and nums2[i] > nums1[j]:
        j += 1

    # 将nums2[i]插入到正确位置
    # 使用逆序遍历将元素后移，避免覆盖
    for k in range(m + i, j, -1):
        nums1[k] = nums1[k - 1]

    # 插入当前元素
    nums1[j] = nums2[i]

    # 更新j指向下一个可能的插入位置
    j += 1

# j=0
# k=0
# for i in range(n):
#
#     while j < m+n and nums2[i] > nums1[j]:
#           j += 1
#     else:
#         if nums1[j] == 0:
#             nums1[j] = nums2[i]
#         nums1.insert(j, nums2[i])
#         j += 1
#
# # while m + n != len(nums1):
# #     nums1.pop()
# print(nums1)









